<?php
/**
 * User: helloJiu
 * Date: 2021/10/14
 * Time: 11:12
 */

namespace App\Algorithm\DP;


class FindCheapestPrice
{
    /**
     * https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye-4/lv-hang-zui-duan-lu-jing
     * 787. K 站中转内最便宜的航班
     * https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/
     * @param Integer $n
     * @param Integer[][] $flights
     * @param Integer $src
     * @param Integer $dst
     * @param Integer $k
     * @return Integer
     */
    function findCheapestPrice($n, $flights, $src, $dst, $k)
    {
        /**
         * 输入:
         * n = 3, edges = [[0,1,100],[1,2,100],[0,2,50]]
         * src = 0, dst = 2, k = 1
         * 输出: 200
         */
        $map = [];
        foreach ($flights as $flight) {
            $from = $flight[0];
            $to = $flight[1];
            $price = $flight[2];
            $map[$to][] = [$from, $price];
        }
        $dp = [];
        $ret = $this->dpm($map, $dst, $k, $src, $dp);
        return $ret;

    }

    /**
     * 获取到达$dst的最小价格
     * @param $map
     * @param $dst
     * @param $k
     * @param $src
     * @param $dp
     * @return int|mixed
     */
    private function dpm(&$map, $dst, $k, $src, &$dp)
    {
        if ($dst == $src) {
            return 0;
        }

        if (!empty($dp[$dst . '|' . $k])) {
            return $dp[$dst . '|' . $k];
        }

        if (!isset($map[$dst])) {
            return -1;
        }

        if ($k == -1) {
            return -1;
        }

        $ingresses = $map[$dst];
        $res = PHP_INT_MAX;
        // [[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
        foreach ($ingresses as $ingress) {
            // var_dump($ingress[0] . '##' . ($k-1) . '--'. $src);
            $price = $this->dpm($map, $ingress[0], $k - 1, $src, $dp);
            if ($price != -1) {
                $res = min($res, $price + $ingress[1]);
            }
        }

        if ($res == PHP_INT_MAX) {
            return -1;
        }
        $dp[$dst . '|' . $k] = $res;
        return $res;
    }

}